home *** CD-ROM | disk | FTP | other *** search
/ Over 1,000 Windows 95 Programs / Over 1000 Windows 95 Programs (Microforum) (Disc 1).iso / 0957 / gnugrep / gui / kwset.c < prev    next >
C/C++ Source or Header  |  1996-07-21  |  22KB  |  752 lines
  1. /* kwset.c - search for any of a set of keywords.
  2.    Copyright 1989 Free Software Foundation
  3.           Written August 1989 by Mike Haertel.
  4.  
  5.    This program is free software; you can redistribute it and/or modify
  6.    it under the terms of the GNU General Public License as published by
  7.    the Free Software Foundation; either version 1, or (at your option)
  8.    any later version.
  9.  
  10.    This program is distributed in the hope that it will be useful,
  11.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.    GNU General Public License for more details.
  14.  
  15.    You should have received a copy of the GNU General Public License
  16.    along with this program; if not, write to the Free Software
  17.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  
  19.    The author may be reached (Email) at the address mike@ai.mit.edu,
  20.    or (US mail) as Mike Haertel c/o Free Software Foundation. */
  21.  
  22. /* The algorithm implemented by these routines bears a startling resemblence
  23.    to one discovered by Beate Commentz-Walter, although it is not identical.
  24.    See "A String Matching Algorithm Fast on the Average," Technical Report,
  25.    IBM-Germany, Scientific Center Heidelberg, Tiergartenstrasse 15, D-6900
  26.    Heidelberg, Germany.  See also Aho, A.V., and M. Corasick, "Efficient
  27.    String Matching:  An Aid to Bibliographic Search," CACM June 1975,
  28.    Vol. 18, No. 6, which describes the failure function used below. */
  29.  
  30. #pragma warning(disable : 4018) //signed/unsigned mismatch
  31.  
  32. #include <limits.h>
  33. #include <stdlib.h>
  34. #include <stddef.h>
  35. #include <sys/types.h>
  36. #include <string.h>
  37. #include <memory.h>
  38.  
  39. extern char *xmalloc(size_t size);
  40. extern char *xrealloc(char *ptr, size_t size);
  41. extern char *xcalloc(int n, size_t size);
  42. extern int xfree(char *ptr);
  43.  
  44. #define malloc xmalloc
  45. #define realloc xrealloc
  46. #define free xfree
  47.  
  48. #include "kwset.h"
  49. #include "obstack.h"
  50.  
  51. #define NCHAR (UCHAR_MAX + 1)
  52. #define obstack_chunk_alloc xmalloc
  53. #define obstack_chunk_free xfree
  54.  
  55. /* Balanced tree of edges and labels leaving a given trie node. */
  56. struct tree
  57. {
  58.   struct tree *llink;        /* Left link; MUST be first field. */
  59.   struct tree *rlink;        /* Right link (to larger labels). */
  60.   struct trie *trie;        /* Trie node pointed to by this edge. */
  61.   unsigned char label;        /* Label on this edge. */
  62.   char balance;            /* Difference in depths of subtrees. */
  63. };
  64.  
  65. /* Node of a trie representing a set of reversed keywords. */
  66. struct trie
  67. {
  68.   unsigned int accepting;    /* Word index of accepted word, or zero. */
  69.   struct tree *links;        /* Tree of edges leaving this node. */
  70.   struct trie *parent;        /* Parent of this node. */
  71.   struct trie *next;        /* List of all trie nodes in level order. */
  72.   struct trie *fail;        /* Aho-Corasick failure function. */
  73.   int depth;            /* Depth of this node from the root. */
  74.   int shift;            /* Shift function for search failures. */
  75.   int maxshift;            /* Max shift of self and descendents. */
  76. };
  77.  
  78. /* Structure returned opaquely to the caller, containing everything. */
  79. struct kwset
  80. {
  81.   struct obstack obstack;    /* Obstack for node allocation. */
  82.   int words;            /* Number of words in the trie. */
  83.   struct trie *trie;        /* The trie itself. */
  84.   int mind;            /* Minimum depth of an accepting node. */
  85.   int maxd;            /* Maximum depth of any node. */
  86.   unsigned char delta[NCHAR];    /* Delta table for rapid search. */
  87.   struct trie *next[NCHAR];    /* Table of children of the root. */
  88.   char *target;            /* Target string if there's only one. */
  89.   int mind2;            /* Used in Boyer-Moore search for one string. */
  90.   char *trans;            /* Character translation table. */
  91. };
  92.  
  93. /* Allocate and initialize a keyword set object, returning an opaque
  94.    pointer to it.  Return NULL if memory is not available. */
  95. kwset_t kwsalloc(char *trans)
  96. //---------------------------
  97. {
  98.   struct kwset *kwset;
  99.  
  100.   kwset = (struct kwset *) malloc(sizeof (struct kwset));
  101.   if (!kwset)
  102.     return 0;
  103.  
  104.   obstack_init(&kwset->obstack);
  105.   kwset->words = 0;
  106.   kwset->trie
  107.     = (struct trie *) obstack_alloc(&kwset->obstack, sizeof (struct trie));
  108.   if (!kwset->trie)
  109.     {
  110.       kwsfree((kwset_t) kwset);
  111.       return 0;
  112.     }
  113.   kwset->trie->accepting = 0;
  114.   kwset->trie->links = 0;
  115.   kwset->trie->parent = 0;
  116.   kwset->trie->next = 0;
  117.   kwset->trie->fail = 0;
  118.   kwset->trie->depth = 0;
  119.   kwset->trie->shift = 0;
  120.   kwset->mind = INT_MAX;
  121.   kwset->maxd = -1;
  122.   kwset->target = 0;
  123.   kwset->trans = trans;
  124.  
  125.   return (kwset_t) kwset;
  126. }
  127.  
  128. /* Add the given string to the contents of the keyword set.  Return NULL
  129.    for success, an error message otherwise. */
  130. char *kwsincr(kwset_t kws, char *text, size_t len)
  131. //------------------------------------------------
  132. { struct kwset *kwset;
  133.   register struct trie *trie;
  134.   register unsigned char label;
  135.   register struct tree *link;
  136.   register int depth;
  137.   struct tree *links[12];
  138.   enum { L, R } dirs[12];
  139.   struct tree *t, *r, *l, *rl, *lr;
  140.  
  141.   kwset = (struct kwset *) kws;
  142.   trie = kwset->trie;
  143.   text += len;
  144.  
  145.   /* Descend the trie (built of reversed keywords) character-by-character,
  146.      installing new nodes when necessary. */
  147.   while (len--)
  148.     {
  149.       label = kwset->trans ? kwset->trans[(unsigned char) *--text] : *--text;
  150.  
  151.       /* Descend the tree of outgoing links for this trie node,
  152.      looking for the current character and keeping track
  153.      of the path followed. */
  154.       link = trie->links;
  155.       links[0] = (struct tree *) &trie->links;
  156.       dirs[0] = L;
  157.       depth = 1;
  158.  
  159.       while (link && label != link->label)
  160.     {
  161.       links[depth] = link;
  162.       if (label < link->label)
  163.         dirs[depth++] = L, link = link->llink;
  164.       else
  165.         dirs[depth++] = R, link = link->rlink;
  166.     }
  167.  
  168.       /* The current character doesn't have an outgoing link at
  169.      this trie node, so build a new trie node and install
  170.      a link in the current trie node's tree. */
  171.       if (!link)
  172.     {
  173.       link = (struct tree *) obstack_alloc(&kwset->obstack,
  174.                            sizeof (struct tree));
  175.       if (!link)
  176.         return "memory exhausted";
  177.       link->llink = 0;
  178.       link->rlink = 0;
  179.       link->trie = (struct trie *) obstack_alloc(&kwset->obstack,
  180.                              sizeof (struct trie));
  181.       if (!link->trie)
  182.         return "memory exhausted";
  183.       link->trie->accepting = 0;
  184.       link->trie->links = 0;
  185.       link->trie->parent = trie;
  186.       link->trie->next = 0;
  187.       link->trie->fail = 0;
  188.       link->trie->depth = trie->depth + 1;
  189.       link->trie->shift = 0;
  190.       link->label = label;
  191.       link->balance = 0;
  192.  
  193.       /* Install the new tree node in its parent. */
  194.       if (dirs[--depth] == L)
  195.         links[depth]->llink = link;
  196.       else
  197.         links[depth]->rlink = link;
  198.  
  199.       /* Back up the tree fixing the balance flags. */
  200.       while (depth && !links[depth]->balance)
  201.         {
  202.           if (dirs[depth] == L)
  203.         --links[depth]->balance;
  204.           else
  205.         ++links[depth]->balance;
  206.           --depth;
  207.         }
  208.  
  209.       /* Rebalance the tree by pointer rotations if necessary. */
  210.       if (depth && ((dirs[depth] == L && --links[depth]->balance)
  211.             || (dirs[depth] == R && ++links[depth]->balance)))
  212.         {
  213.           switch (links[depth]->balance)
  214.         {
  215.         case (char) -2:
  216.           switch (dirs[depth + 1])
  217.             {
  218.             case L:
  219.               r = links[depth], t = r->llink, rl = t->rlink;
  220.               t->rlink = r, r->llink = rl;
  221.               t->balance = r->balance = 0;
  222.               break;
  223.             case R:
  224.               r = links[depth], l = r->llink, t = l->rlink;
  225.               rl = t->rlink, lr = t->llink;
  226.               t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl;
  227.               l->balance = t->balance != 1 ? 0 : -1;
  228.               r->balance = t->balance != (char) -1 ? 0 : 1;
  229.               t->balance = 0;
  230.               break;
  231.             }
  232.           break;
  233.         case 2:
  234.           switch (dirs[depth + 1])
  235.             {
  236.             case R:
  237.               l = links[depth], t = l->rlink, lr = t->llink;
  238.               t->llink = l, l->rlink = lr;
  239.               t->balance = l->balance = 0;
  240.               break;
  241.             case L:
  242.               l = links[depth], r = l->rlink, t = r->llink;
  243.               lr = t->llink, rl = t->rlink;
  244.               t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl;
  245.               l->balance = t->balance != 1 ? 0 : -1;
  246.               r->balance = t->balance != (char) -1 ? 0 : 1;
  247.               t->balance = 0;
  248.               break;
  249.             }
  250.           break;
  251.         }
  252.  
  253.           if (dirs[depth - 1] == L)
  254.         links[depth - 1]->llink = t;
  255.           else
  256.         links[depth - 1]->rlink = t;
  257.         }
  258.     }
  259.  
  260.       trie = link->trie;
  261.     }
  262.  
  263.   /* Mark the node we finally reached as accepting, encoding the
  264.      index number of this word in the keyword set so far. */
  265.   if (!trie->accepting)
  266.     trie->accepting = 1 + 2 * kwset->words;
  267.   ++kwset->words;
  268.  
  269.   /* Keep track of the longest and shortest string of the keyword set. */
  270.   if (trie->depth < kwset->mind)
  271.     kwset->mind = trie->depth;
  272.   if (trie->depth > kwset->maxd)
  273.     kwset->maxd = trie->depth;
  274.  
  275.   return 0;
  276. }
  277.  
  278. /* Enqueue the trie nodes referenced from the given tree in the
  279.    given queue. */
  280. static void enqueue(struct tree *tree, struct trie **last)
  281. //--------------------------------------------------------
  282. {
  283.   if (!tree)
  284.     return;
  285.   enqueue(tree->llink, last);
  286.   enqueue(tree->rlink, last);
  287.   (*last) = (*last)->next = tree->trie;
  288. }
  289.  
  290. /* Compute the Aho-Corasick failure function for the trie nodes referenced
  291.    from the given tree, given the failure function for their parent as
  292.    well as a last resort failure node. */
  293. static void treefails(register struct tree *tree, struct trie *fail, struct trie *recourse)
  294. //-----------------------------------------------------------------------------------------
  295. { register struct tree *link;
  296.  
  297.   if (!tree)
  298.     return;
  299.  
  300.   treefails(tree->llink, fail, recourse);
  301.   treefails(tree->rlink, fail, recourse);
  302.  
  303.   /* Find, in the chain of fails going back to the root, the first
  304.      node that has a descendent on the current label. */
  305.   while (fail)
  306.     {
  307.       link = fail->links;
  308.       while (link && tree->label != link->label)
  309.     if (tree->label < link->label)
  310.       link = link->llink;
  311.     else
  312.       link = link->rlink;
  313.       if (link)
  314.     {
  315.       tree->trie->fail = link->trie;
  316.       return;
  317.     }
  318.       fail = fail->fail;
  319.     }
  320.  
  321.   tree->trie->fail = recourse;
  322. }
  323.  
  324. /* Set delta entries for the links of the given tree such that
  325.    the preexisting delta value is larger than the current depth. */
  326. static void treedelta(register struct tree *tree, register unsigned int depth, 
  327.                                             unsigned char delta[])
  328. //----------------------------------------------------------------------------
  329. { if (!tree)
  330.     return;
  331.   treedelta(tree->llink, depth, delta);
  332.   treedelta(tree->rlink, depth, delta);
  333.   if (depth < delta[tree->label])
  334.     delta[tree->label] = depth;
  335. }
  336.  
  337. /* Return true if A has every label in B. */
  338. static int hasevery(register struct tree *a, register struct tree *b)
  339. //-------------------------------------------------------------------
  340. { if (!b)
  341.     return 1;
  342.   if (!hasevery(a, b->llink))
  343.     return 0;
  344.   if (!hasevery(a, b->rlink))
  345.     return 0;
  346.   while (a && b->label != a->label)
  347.     if (b->label < a->label)
  348.       a = a->llink;
  349.     else
  350.       a = a->rlink;
  351.   return !!a;
  352. }
  353.  
  354. /* Compute a vector, indexed by character code, of the trie nodes
  355.    referenced from the given tree. */
  356. static void treenext(struct tree *tree, struct trie *next[])
  357. //----------------------------------------------------------     
  358. { if (!tree)
  359.     return;
  360.   treenext(tree->llink, next);
  361.   treenext(tree->rlink, next);
  362.   next[tree->label] = tree->trie;
  363. }
  364.  
  365. /* Compute the shift for each trie node, as well as the delta
  366.    table and next cache for the given keyword set. */
  367. char *kwsprep(kwset_t kws)
  368. //------------------------
  369. { register struct kwset *kwset;
  370.   register int i;
  371.   register struct trie *curr, *fail;
  372.   register char *trans;
  373.   unsigned char delta[NCHAR];
  374.   struct trie *last, *next[NCHAR];
  375.  
  376.   kwset = (struct kwset *) kws;
  377.  
  378.   /* Initial values for the delta table; will be changed later.  The
  379.      delta entry for a given character is the smallest depth of any
  380.      node at which an outgoing edge is labeled by that character. */
  381.   if (kwset->mind < 256)
  382.     for (i = 0; i < NCHAR; ++i)
  383.       delta[i] = kwset->mind;
  384.   else
  385.     for (i = 0; i < NCHAR; ++i)
  386.       delta[i] = 255;
  387.  
  388.   /* Check if we can use the simple boyer-moore algorithm, instead
  389.      of the hairy commentz-walter algorithm. */
  390.   if (kwset->words == 1 && kwset->trans == 0)
  391.     {
  392.       /* Looking for just one string.  Extract it from the trie. */
  393.       kwset->target = obstack_alloc(&kwset->obstack, kwset->mind);
  394.       for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i)
  395.     {
  396.       kwset->target[i] = curr->links->label;
  397.       curr = curr->links->trie;
  398.     }
  399.       /* Build the Boyer Moore delta.  Boy that's easy compared to CW. */
  400.       for (i = 0; i < kwset->mind; ++i)
  401.     delta[(unsigned char) kwset->target[i]] = kwset->mind - (i + 1);
  402.       kwset->mind2 = kwset->mind;
  403.       /* Find the minimal delta2 shift that we might make after
  404.      a backwards match has failed. */
  405.       for (i = 0; i < kwset->mind - 1; ++i)
  406.     if (kwset->target[i] == kwset->target[kwset->mind - 1])
  407.       kwset->mind2 = kwset->mind - (i + 1);
  408.     }
  409.   else
  410.     {
  411.       /* Traverse the nodes of the trie in level order, simultaneously
  412.      computing the delta table, failure function, and shift function. */
  413.       for (curr = last = kwset->trie; curr; curr = curr->next)
  414.     {
  415.       /* Enqueue the immediate descendents in the level order queue. */
  416.       enqueue(curr->links, &last);
  417.  
  418.       curr->shift = kwset->mind;
  419.       curr->maxshift = kwset->mind;
  420.  
  421.       /* Update the delta table for the descendents of this node. */
  422.       treedelta(curr->links, curr->depth, delta);
  423.  
  424.       /* Compute the failure function for the decendents of this node. */
  425.       treefails(curr->links, curr->fail, kwset->trie);
  426.  
  427.       /* Update the shifts at each node in the current node's chain
  428.          of fails back to the root. */
  429.       for (fail = curr->fail; fail; fail = fail->fail)
  430.         {
  431.           /* If the current node has some outgoing edge that the fail
  432.          doesn't, then the shift at the fail should be no larger
  433.          than the difference of their depths. */
  434.           if (!hasevery(fail->links, curr->links))
  435.         if (curr->depth - fail->depth < fail->shift)
  436.           fail->shift = curr->depth - fail->depth;
  437.  
  438.           /* If the current node is accepting then the shift at the
  439.          fail and its descendents should be no larger than the
  440.          difference of their depths. */
  441.           if (curr->accepting && fail->maxshift > curr->depth - fail->depth)
  442.         fail->maxshift = curr->depth - fail->depth;
  443.         }
  444.     }
  445.  
  446.       /* Traverse the trie in level order again, fixing up all nodes whose
  447.      shift exceeds their inherited maxshift. */
  448.       for (curr = kwset->trie->next; curr; curr = curr->next)
  449.     {
  450.       if (curr->maxshift > curr->parent->maxshift)
  451.         curr->maxshift = curr->parent->maxshift;
  452.       if (curr->shift > curr->maxshift)
  453.         curr->shift = curr->maxshift;
  454.     }
  455.  
  456.       /* Create a vector, indexed by character code, of the outgoing links
  457.      from the root node. */
  458.       for (i = 0; i < NCHAR; ++i)
  459.     next[i] = 0;
  460.       treenext(kwset->trie->links, next);
  461.  
  462.       if ((trans = kwset->trans) != 0)
  463.     for (i = 0; i < NCHAR; ++i)
  464.       kwset->next[i] = next[(unsigned char) trans[i]];
  465.       else
  466.     for (i = 0; i < NCHAR; ++i)
  467.       kwset->next[i] = next[i];
  468.     }
  469.  
  470.   /* Fix things up for any translation table. */
  471.   if ((trans = kwset->trans) != 0)
  472.     for (i = 0; i < NCHAR; ++i)
  473.       kwset->delta[i] = delta[(unsigned char) trans[i]];
  474.   else
  475.     for (i = 0; i < NCHAR; ++i)
  476.       kwset->delta[i] = delta[i];
  477.  
  478.   return 0;
  479. }
  480.  
  481. #define U(C) ((unsigned char) (C))
  482.  
  483. /* Fast boyer-moore search. */
  484. static char *bmexec(kwset_t kws, char *text, size_t size)
  485. //-------------------------------------------------------
  486. { struct kwset *kwset;
  487.   register unsigned char *d1;
  488.   register char *ep, *sp, *tp;
  489.   register int d, gc, i, len, md2;
  490.  
  491.   kwset = (struct kwset *) kws;
  492.   len = kwset->mind;
  493.  
  494.   if (len == 0)
  495.     return text;
  496.   if (len > size)
  497.     return 0;
  498.   if (len == 1)
  499.     return memchr(text, kwset->target[0], size);
  500.  
  501.   d1 = kwset->delta;
  502.   sp = kwset->target + len;
  503.   gc = U(sp[-2]);
  504.   md2 = kwset->mind2;
  505.   tp = text + len;
  506.  
  507.   /* Significance of 12: 1 (initial offset) + 10 (skip loop) + 1 (md2). */
  508.   if (size > 12 * len)
  509.     /* 11 is not a bug, the initial offset happens only once. */
  510.     for (ep = text + size - 11 * len;;)
  511.       {
  512.     while (tp <= ep)
  513.       {
  514.         d = d1[U(tp[-1])], tp += d;
  515.         d = d1[U(tp[-1])], tp += d;
  516.         if (d == 0)
  517.           goto found;
  518.         d = d1[U(tp[-1])], tp += d;
  519.         d = d1[U(tp[-1])], tp += d;
  520.         d = d1[U(tp[-1])], tp += d;
  521.         if (d == 0)
  522.           goto found;
  523.         d = d1[U(tp[-1])], tp += d;
  524.         d = d1[U(tp[-1])], tp += d;
  525.         d = d1[U(tp[-1])], tp += d;
  526.         if (d == 0)
  527.           goto found;
  528.         d = d1[U(tp[-1])], tp += d;
  529.         d = d1[U(tp[-1])], tp += d;
  530.       }
  531.     break;
  532.       found:
  533.     if (U(tp[-2]) == gc)
  534.       {
  535.         for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)
  536.           ;
  537.         if (i > len)
  538.           return tp - len;
  539.       }
  540.     tp += md2;
  541.       }
  542.  
  543.   /* Now we have only a few characters left to search.  We
  544.      carefully avoid ever producing an out-of-bounds pointer. */
  545.   ep = text + size;
  546.   d = d1[U(tp[-1])];
  547.   while (d <= ep - tp)
  548.     {
  549.       d = d1[U((tp += d)[-1])];
  550.       if (d != 0)
  551.     continue;
  552.       if (tp[-2] == gc)
  553.     {
  554.       for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)
  555.         ;
  556.       if (i > len)
  557.         return tp - len;
  558.     }
  559.       d = md2;
  560.     }
  561.  
  562.   return 0;
  563. }
  564.  
  565. /* Hairy multiple string search. */
  566. static char *cwexec(kwset_t kws, char *text, size_t len, struct kwsmatch *kwsmatch)
  567. //---------------------------------------------------------------------------------
  568. { struct kwset *kwset;
  569.   struct trie **next, *trie, *accept;
  570.   char *beg, *lim, *mch, *lmch;
  571.   register unsigned char c, *delta;
  572.   register int d;
  573.   register char *end, *qlim;
  574.   register struct tree *tree;
  575.   register char *trans;
  576.  
  577.   /* Initialize register copies and look for easy ways out. */
  578.   kwset = (struct kwset *) kws;
  579.   if (len < kwset->mind)
  580.     return 0;
  581.   next = kwset->next;
  582.   delta = kwset->delta;
  583.   trans = kwset->trans;
  584.   lim = text + len;
  585.   end = text;
  586.   if ((d = kwset->mind) != 0)
  587.     mch = 0;
  588.   else
  589.     {
  590.       mch = text, accept = kwset->trie;
  591.       goto match;
  592.     }
  593.  
  594.   if (len >= 4 * kwset->mind)
  595.     qlim = lim - 4 * kwset->mind;
  596.   else
  597.     qlim = 0;
  598.  
  599.   while (lim - end >= d)
  600.     {
  601.       if (qlim && end <= qlim)
  602.     {
  603.       end += d - 1;
  604.       while ((d = delta[c = *end]) && end < qlim)
  605.         {
  606.           end += d;
  607.           end += delta[(unsigned char) *end];
  608.           end += delta[(unsigned char) *end];
  609.         }
  610.       ++end;
  611.     }
  612.       else
  613.     d = delta[c = (end += d)[-1]];
  614.       if (d)
  615.     continue;
  616.       beg = end - 1;
  617.       trie = next[c];
  618.       if (trie->accepting)
  619.     {
  620.       mch = beg;
  621.       accept = trie;
  622.     }
  623.       d = trie->shift;
  624.       while (beg > text)
  625.     {
  626.       c = trans ? trans[(unsigned char) *--beg] : *--beg;
  627.       tree = trie->links;
  628.       while (tree && c != tree->label)
  629.         if (c < tree->label)
  630.           tree = tree->llink;
  631.         else
  632.           tree = tree->rlink;
  633.       if (tree)
  634.         {
  635.           trie = tree->trie;
  636.           if (trie->accepting)
  637.         {
  638.           mch = beg;
  639.           accept = trie;
  640.         }
  641.         }
  642.       else
  643.         break;
  644.       d = trie->shift;
  645.     }
  646.       if (mch)
  647.     goto match;
  648.     }
  649.   return 0;
  650.  
  651.  match:
  652.   /* Given a known match, find the longest possible match anchored
  653.      at or before its starting point.  This is nearly a verbatim
  654.      copy of the preceding main search loops. */
  655.   if (lim - mch > kwset->maxd)
  656.     lim = mch + kwset->maxd;
  657.   lmch = 0;
  658.   d = 1;
  659.   while (lim - end >= d)
  660.     {
  661.       if ((d = delta[c = (end += d)[-1]]) != 0)
  662.     continue;
  663.       beg = end - 1;
  664.       if (!(trie = next[c]))
  665.     {
  666.       d = 1;
  667.       continue;
  668.     }
  669.       if (trie->accepting && beg <= mch)
  670.     {
  671.       lmch = beg;
  672.       accept = trie;
  673.     }
  674.       d = trie->shift;
  675.       while (beg > text)
  676.     {
  677.       c = trans ? trans[(unsigned char) *--beg] : *--beg;
  678.       tree = trie->links;
  679.       while (tree && c != tree->label)
  680.         if (c < tree->label)
  681.           tree = tree->llink;
  682.         else
  683.           tree = tree->rlink;
  684.       if (tree)
  685.         {
  686.           trie = tree->trie;
  687.           if (trie->accepting && beg <= mch)
  688.         {
  689.           lmch = beg;
  690.           accept = trie;
  691.         }
  692.         }
  693.       else
  694.         break;
  695.       d = trie->shift;
  696.     }
  697.       if (lmch)
  698.     {
  699.       mch = lmch;
  700.       goto match;
  701.     }
  702.       if (!d)
  703.     d = 1;
  704.     }
  705.  
  706.   if (kwsmatch)
  707.     {
  708.       kwsmatch->index = accept->accepting / 2;
  709.       kwsmatch->beg[0] = mch;
  710.       kwsmatch->size[0] = accept->depth;
  711.     }
  712.   return mch;
  713. }
  714.   
  715. /* Search through the given text for a match of any member of the
  716.    given keyword set.  Return a pointer to the first character of
  717.    the matching substring, or NULL if no match is found.  If FOUNDLEN
  718.    is non-NULL store in the referenced location the length of the
  719.    matching substring.  Similarly, if FOUNDIDX is non-NULL, store
  720.    in the referenced location the index number of the particular
  721.    keyword matched. */
  722. char *kwsexec(kwset_t kws, char *text, size_t size, struct kwsmatch *kwsmatch)
  723. //----------------------------------------------------------------------------
  724. { struct kwset *kwset;
  725.   char *ret;
  726.  
  727.   kwset = (struct kwset *) kws;
  728.   if (kwset->words == 1 && kwset->trans == 0)
  729.     {
  730.       ret = bmexec(kws, text, size);
  731.       if (kwsmatch != 0 && ret != 0)
  732.     {
  733.       kwsmatch->index = 0;
  734.       kwsmatch->beg[0] = ret;
  735.       kwsmatch->size[0] = kwset->mind;
  736.     }
  737.       return ret;
  738.     }
  739.   else
  740.     return cwexec(kws, text, size, kwsmatch);
  741. }
  742.  
  743. /* Free the components of the given keyword set. */
  744. void kwsfree(kwset_t kws)
  745. //-----------------------
  746. { struct kwset *kwset;
  747.  
  748.   kwset = (struct kwset *) kws;
  749.   obstack_free(&kwset->obstack, 0);
  750.   free(kws);
  751. }
  752.